#include<stdio.h>
#include<string.h>

typedef struct COVER
{
	int b[15][15];//B矩阵
	int lineedge[15];//行界值
	int rowedge[15];//列界值
	int linecover[15];//行覆盖标记，只能取0，1
	int rowcover[15];//列覆盖标记，只能取0，1
	int sy[15];//如果k列被搜索过，则sy[k]为1；否则为0；
	int xr[15];
	int yr[15];
	int r;//r为最大配对数（最小覆盖数 ）,xr和yr分别为对应的配对,无配对的为0
	int m;//B矩阵中未覆盖的最小值
	int n;//B矩阵的大小
} Cover;
typedef struct MAT
{                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
	int c[15][15];//初始邻接矩阵
	Cover cov;
	int n;//C矩阵的大小
} Mat;



void Ini(Mat *mat)
{
	int i,j;
	(mat->cov).n=mat->n;
	for(i=0;i<mat->n;i++)
	{
		(mat->cov).lineedge[i]=10000;
		for(j=0;j<mat->n;j++)
		{
			if(mat->c[i][j]<(mat->cov).lineedge[i])
			(mat->cov).lineedge[i]=mat->c[i][j];
		}
	}//行界值的初始化
	
	for(j=0;j<mat->n;j++)
		(mat->cov).rowedge[j]=0;//列界值的初始化
	
	for(i=0;i<mat->n;i++)
			for(j=0;j<mat->n;j++)		
				(mat->cov).b[i][j]=mat->c[i][j]-(mat->cov).lineedge[i]-(mat->cov).rowedge[j];
	//Ｂ矩阵的初始化
			
	(mat->cov).r=0;//r的初始值为0；
	(mat->cov).m=10000;//m的初始值为最大，10000
}//初始化

void cover(Cover *cov)
{
	int i,j,t;
	memset(	cov->sy,0,sizeof(cov->sy));
	memset(	cov->xr,-1,sizeof(cov->xr));
	memset(cov->yr,-1,sizeof(cov->yr));
	cov->r=0;
	for(j=0;j<cov->n;j++)
	{
		if(cov->xr[j]==-1)//xr的初始值为－1
		{
			memset(	cov->sy,0,sizeof(cov->sy));
			cov->r+=path(cov,j);
		}
	}//获得最大匹配如果i有相关匹配，那么xr[i]=j，否则xr[i]=-1。cov->r为最大匹配数
	for(i=0,j=0;i<cov->n,j<cov->r;i++)//任取cov->r行构成一个覆盖，
	{
		if(cov->xr[i]!=-1)//如果i的相关邻接点有匹配，那么把i作为一个初始覆盖行
		{
			j++;	
			cov->linecover[i]=1;	//覆盖用1 表示。
		}
	}
	
	while((t=zeroexist(cov))&&t!=-1)//直到cov里面不含0元素为止
	{
		int k;
		i=t/cov->n;
		j=t%cov->n;//i,j点为不属于R覆盖的0点
		
		for(k=0;k<cov->n;k++)
		{
			if(cov->linecover[k]==1&&cov->xr[k]==j)//k属于R。k，j属于R覆盖区。i，j不属于R覆盖区。用k覆盖只能覆盖k这一行，用j覆盖，能够同时覆盖上k,j和i,j两个0点。
			{
				cov->rowcover[j]=1;
				cov->linecover[k]=0;
			}
		}
	}//此时已经选出最小覆盖。
	
}//对mat的当前B矩阵进行最小覆盖，当r＝n时，返回0，当r<n时，返回1，并且对B矩阵进行重构。

int zeroexist(Cover *cov)
{
	int i,j;
	for(i=0;i<cov->n;i++)
	{
		if(!cov->linecover[i])//linecover表示的是第i行被覆盖。
		{
			for(j=0;j<cov->n;j++)
			{
				if(!cov->rowcover[j]&&!cov->b[i][j])	
					return (cov->n)*i+j;//含０返回 n＊i＋j对该点进行标记。
			}
		}
	}
	return -1;//不含０返回-１
}//判断当前的覆盖是否是完全覆盖

void change(Cover *cov)
{
	int i,j;
	for(i=0;i<cov->n;i++)
	{
		if(!cov->linecover[i])
		{
			for(j=0;j<cov->n;j++)
			{
				if((!cov->rowcover[j])&&cov->b[i][j]<cov->m)
				{
					cov->m=cov->b[i][j];//选出未覆盖元素中的最非0值
				}
			}		
		}
	}
	
	for(i=0;i<cov->n;i++)
	{
		for(j=0;j<cov->n;j++)
		{
			if(cov->linecover[i]&&cov->rowcover[j])
			cov->b[i][j]+=cov->m;
			if(!cov->linecover[i]&&!cov->rowcover[j])
			cov->b[i][j]-=cov->m;
		}
	}
	
	for(i=0;i<cov->n;i++)
	{
		if(!cov->linecover[i])
			cov->lineedge[i]+=cov->m;//修改界值
		else cov->linecover[i]=0;//删除覆盖标记
		if(cov->rowcover[i])
		{
			cov->rowedge[i]-=cov->m;//修改界值
			cov->rowcover[i]=0;//删除覆盖标记
		}
	}
}//修改，Ｂ，Ｂ的界值，并删除覆盖标记

int path(Cover *cov,int u)//是否找到增广路的判定，如果找到增广路，则给相应需要改变的节点进行标注。
{
	int i;
	for(i=0;i<cov->n;i++)
	{
		if(!cov->b[u][i]&&!cov->sy[i])
		{
			cov->sy[i]=1;
			if(cov->yr[i]==-1 || path(cov,cov->yr[i]))
			{
				cov->xr[u]=i;
				cov->yr[i]=u;
				return 1;
			}
		}
	}
	return 0;
}
